This invention relates to max-log-APP decoding and is particularly concerned with max-log-APP decoder systems and methods suited for Turbo and Turbo-like forward-error-correcting codes, by using iterative processing.
Claude Berrou obtained U.S. Pat. No. 4,446,747 entitled: xe2x80x9cError-correction coding method with at least two systematic convolutional codings in parallel, corresponding iterative decoding method, decoding module and decoderxe2x80x9d. This patent describes essentially the same Turbo-code presented by Berrou et al in their paper xe2x80x9cNear Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codesxe2x80x9d, published in the Proceedings of ICC""93, Geneva, Switzerland, pp. 1064-1070, May, 1993. The Turbo-code presented, is a rate 1/2 binary code that provided performance within 0.5 dB of the BPSK capacity limit at a BER of 10xe2x88x925, when using an interleaver block size of 65,536. This result is also only 0.7 dB from the more general Shannon capacity limit. The encoder consists of two rate 1/2 recursive systematic convolutional (RSC) encoders operating in parallel with the data binary digits (bits) interleaved between the two encoders as shown in FIG. 1. Without puncturing, and with rate 1/2 constituent codes, the overall code rate is 1/3. This is because the systematic data bits only need to be sent once. Other code rates can be achieved as required by puncturing the parity bits c1i and c2i. In this configuration, the job of the interleaver is to spread reliability information that occurs in one code throughout the other code so that there is a higher probability of correcting unreliable information. FIG. 2 shows the RSC encoder, with polynomials (23,35)8, used in the prior art TURBO4 codec as discussed in B. Talibart and C. Berrou, xe2x80x9cNotice Preliminaire du Circuit Turbo-Codeur/Decodeur TURBO4xe2x80x9d, Version 0.0, June, 1995. This RSC encoder has four memory (delay) units.
More recently Berrou, and Glavieux provided more discussion of the coding and decoding of Turbo-codes in their paper xe2x80x9cNear Optimum Error Correcting Coding and Decoding: Turbo-Codesxe2x80x9d, published in the IEEE Trans. on Comm., Vol. 44, No. 10, October 1996.
Soft-in/soft-out a posterior probability (APP) decoding of the systematic component codes is key to the decoding of Turbo-codes. This is also referred to as maximum a posterior (MAP) decoding in the literature. The so-called MAP algorithm was first derived by Bahl et al in their paper xe2x80x9cOptimal Decoding of Linear Codes for Minimizing Symbol Error Ratexe2x80x9d, published in IEEE Trans. on Inform. Theory, Vol. IT-20, pp. 284-287, March 1974. The APP terminology is more correct in the context of soft-in/soft-out iterative processing, and this is the terminology used here.
An APP decoder finds the probability of each data bit at each bit time given the entire received signal. Thus it also inherently provides the most likely bit value at each bit time given the entire received signal. This is in contrast to the well-known Viterbi algorithm, which performs maximum likelihood sequence estimation (MLSE) as discussed in A. Viterbi, xe2x80x9cError Bounds for Convolutional Codes and an Asymptotically optimum Decoding Algorithmxe2x80x9d, IEEE Trans. Inform. Theory, Vol. IT-13, pp. 260-269, April 1967; and G. Forney, xe2x80x9cThe Viterbi Algorithmxe2x80x9d, Proc. IEEE, Vol. 61, No. 3, pp. 268-278, March 1973. That is, the Viterbi algorithm finds the entire sequence that was most likely transmitted given the received signal. Both algorithms are optimum for their respective criteria, but the APP decoding approach more naturally provides the soft information required for iterative decoding. The relationship between these two decoding methods will be further explained below.
The following is a brief summary of the relevant background material required for understanding the invention. The APP, log-APP, and max-log-APP decoding algorithms are described. A more detailed description of these prior art algorithms is provided in, for example, L. Bahl, J. Cocke, F. Jelinek, and J. Raviv, xe2x80x9cOptimal Decoding of Linear Codes for Minimizing Symbol Error Ratexe2x80x9d, IEEE Trans. on Inform. Theory, Vol. IT-20, pp. 284-287, March 1974; P. Robertson, E. Villebrun, and P. Hoeher, xe2x80x9cA Comparison of Optimal and Sub-Optimal MAP Decoding Algorithms Operating in the Log Domainxe2x80x9d, Proceedings of ICC""95, Seattle, pp. 1009-1013, June 1995; P. Robertson, P. Hoeher, and E. Villebrun, xe2x80x9cOptimal and Sub-Optimal Maximum a Posteriori Algorithms Suitable for Turbo Decodingxe2x80x9d, IEEE Communications Theory, Vol. 8, No. 2, pp. 119-125, March-April 1997. S. Pietrobon, xe2x80x9cImplementation and Performance of a Turbo/MAP Decoderxe2x80x9d, submitted to the International Journal of Satellite Communications, Feb. 21, 1997; J. Hagenauer, E. Offer, and L. Papke, xe2x80x9cIterative Decoding of Binary Block and Convolutional Codesxe2x80x9d, IEEE Trans. on Inform Theory, Vol. 42, No. 2, pp. 429-445, March 1996; J. Erfanian, S. Pasupathy, G. Gulak, xe2x80x9cReduced Complexity Symbol Detectors with Parallel Structures for ISI Channelsxe2x80x9d, IEEE Trans. on Communications, Vol. 42, No. 2/3/4, pp.1661-1671, February/March/April 1994.
The decoding algorithms are presented in the context of systematic binary convolutional codes and an additive white Gaussian noise (AWGN) channel model. Of course this does not prevent their use in other systems with more complicated signaling constellations and channels. In the case of Turbo-codes, recursive systematic convolutional (RSC) codes are conventionally employed.
The prior art APP decoding algorithm is now described. The data bit at time i is denoted as di and is either 0 or 1. The state of the RSC encoder at time i is determined by the contents of the encoder""s shift-register before di enters the encoder. Thus, data bit di causes the state of the encoder to change from Si to Si+1. The initial state S1 is usually set to zero. Here it is assumed that after K systematic bits the final state, SK+1, is also zero. In the case of RSC codes the last mem systematic bits are often reserved and specifically chosen to flush or terminate the encoder into the zero state, where mem is the memory of the RSC encoder. The number of states is Ns=2mem. The usual approach with Turbo-codes is to terminate the first RSC code, interleave the data and flush bits, and then leave the second RSC code unterminated.
Assuming a rate 1/2 RSC encoder, as shown in FIG. 2 for example, the outputs at time i are the systematic data bit di and the coded parity bit ci. These outputs are typically modulated using an antipodal signaling scheme such as BPSK or QPSK and sent through an additive white Gaussian noise (AWGN) channel. The received sequence is defined as
R=[x1y1 . . . xiyi . . . xKyK]xe2x80x83xe2x80x83(1)
where (xi, yi) is a pair of received signal samples at time i, and
xi=dixe2x80x2+ui, dixe2x80x2=1xe2x88x922dixe2x80x83xe2x80x83(2)
yi=cixe2x80x2+vi, cixe2x80x2=1xe2x88x922cixe2x80x83xe2x80x83(3)
where dxe2x80x2i and cxe2x80x2i are the corresponding data and parity symbols with xc2x11 values, and ui and vi are AWGN samples with variance "sgr"2. The likelihood ratio associated with each data bit at time i is given by                               λ          i                =                              Pr            ⁢                          xe2x80x83                        ⁢                          (                                                d                  i                                =                                  0                  ❘                  R                                            )                                            Pr            ⁢                          xe2x80x83                        ⁢                          (                                                d                  i                                =                                  1                  ❘                  R                                            )                                                          (        4        )            
where Pr(di=d|R), d=0, 1 is the a posterior probability (APP) of the data bit di. Once xcexi is evaluated, decisions can be made as follows                                           d            ^                    i                =                  {                                                    0                                                                                  if                    ⁢                                          xe2x80x83                                        ⁢                                          λ                      i                                                        ≥                  1                                                                                    1                                                                                  if                    ⁢                                          xe2x80x83                                        ⁢                                          λ                      i                                                         less than                   1                                                                                        (        5        )            
The efficient method of calculating xcexi can be summarized as follows:                               λ          i                =                                            ∑                              m                =                0                                                              N                  s                                -                1                                      ⁢                                          α                i                m                            ⁢                              δ                i                                  0                  ,                  m                                            ⁢                              β                                  i                  +                  1                                                  f                  ⁡                                      (                                          0                      ,                      m                                        )                                                                                                          ∑                              m                =                0                                                              N                  s                                -                1                                      ⁢                                          α                i                m                            ⁢                              δ                i                                  1                  ,                  m                                            ⁢                              β                                  i                  +                  1                                                  f                  ⁡                                      (                                          1                      ,                      m                                        )                                                                                                          (        6        )            
where m is the state number and the summations are over all Ns states. The xcex1""s and xcex2""s are the forward and backward state metrics, respectively, and the xcex4""s are the branch metrics. The notation f(d,m) refers to the next forward state given input data bit d and current state m. Similarly, the notation b(d,m) refers to the next backward state given input d. The forward state metrics are updated recursively using                               α          i          m                =                              ∑                          d              =              0                        1                    ⁢                                    α                              i                -                1                                            b                ⁡                                  (                                      d                    ,                    m                                    )                                                      ⁢                          δ                              i                -                1                                            d                ,                                  b                  ⁡                                      (                                          d                      ,                      m                                        )                                                                                                          (        7        )            
The backward state metrics are updated recursively using                               β          i          m                =                              ∑                          d              =              0                        1                    ⁢                                    δ              i                              d                ,                m                                      ⁢                          β                              i                +                1                                            f                ⁡                                  (                                      d                    ,                    m                                    )                                                                                        (        8        )            
Given the assumed signal and channel model, and assuming no a priori information about the bits (a priori information can easily be incorporated if desired), the branch metrics are given by
xcex4id,m=Ki exp(xe2x88x92Lc(xid+yicd,m))xe2x80x83xe2x80x83(9)
or,
xcex4id,m=Kixe2x80x2 exp(Lc/2(xidxe2x80x2+yicxe2x80x2d,m))xe2x80x83xe2x80x83(10)
where Ki and Kxe2x80x2i are constants independent of the data and coded bits, Lc=2/"sgr"2=4Es/N0 is called the reliability value of the channel, and cd,m is the coded bit given input bit d with the encoder in state m. Recall that dxe2x80x2 and cxe2x80x2 are the corresponding xc2x11 transmission symbols as defined in (2) and (3). Constants Ki and Kxe2x80x2i can be ignored or used to normalize the state metrics since they cancel in (6).
Substituting (9) or (10) into (6) gives
xcexi=exp(Lcxi)xcex6ixe2x80x83xe2x80x83(11)
where                               ζ          i                =                                            ∑                              m                =                0                                                              N                  s                                -                1                                      ⁢                                          α                i                m                            ⁢              exp              ⁢                              xe2x80x83                            ⁢                              (                                                      -                                          L                      c                                                        ⁢                                      y                    i                                    ⁢                                      c                                          0                      ,                      m                                                                      )                            ⁢                              β                                  i                  +                  1                                                  f                  ⁡                                      (                                          0                      ,                      m                                        )                                                                                                          ∑                              m                =                0                                                              N                  s                                -                1                                      ⁢                                          α                i                m                            ⁢              exp              ⁢                              xe2x80x83                            ⁢                              (                                                      -                                          L                      c                                                        ⁢                                      y                    i                                    ⁢                                      c                                          1                      ,                      m                                                                      )                            ⁢                              β                                  i                  +                  1                                                  f                  ⁡                                      (                                          1                      ,                      m                                        )                                                                                                          (        12        )            
is the extrinsic information factor, used to correct the original systematic information to minimize the probability of decoding error.
The APP decoding algorithm is implemented by first calculating the xcex1""s in the forward direction and storing the results. The xcex2""s are then calculated in the reverse direction. The xcex""s can be calculated at the same time as the xcex2""s to reduce the memory requirement for the xcex2""s and to reduce the number of operations required for the xcex""s by reusing intermediate xcex2 calculations. It is clear from (6) and (8) what products can be reused. If the encoder starts in the zero state then we initialize xcex110=1 and xcex11m=0 for mxe2x89xa00. If the encoder ends in the zero state then we initialize xcex2K+101 and xcex2K+1m=0 for mxe2x89xa00. If the encoder ends in an unknown state then it is appropriate to initialize all xcex2""s to 1, or some other non-zero value.
The log-APP decoding algorithm is now described. Converting to the log domain we define
Li=ln(xcexi)xe2x80x83xe2x80x83(13)
Aim=ln(xcex1im)xe2x80x83xe2x80x83(14)
Bim=ln(xcex2im)xe2x80x83xe2x80x83(15)
Did,m=ln(xcex4id,m)xe2x80x83xe2x80x83(16)
The following operation can also be defined, using the well-known Jacobi""s logarithm function, as described in P. Robertson, E. Villebrun, and P. Hoeher, xe2x80x9cA Comparison of Optimal and Sub-Optimal MAP Decoding Algorithms Operating in the Log Domainxe2x80x9d, Proceedings of ICC""95, Seattle, pp. 1009-1013, June 1995; P. Robertson, P. Hoeher, and E. Villebrun, xe2x80x9cOptimal and Sub-Optimal Maximum a Posteriori Algorithms Suitable for Turbo Decodingxe2x80x9d, IEEE Communications Theory, Vol. 8, No. 2, pp. 119-125, March-April 1997; S. Pietrobon, xe2x80x9cImplementation and Performance of a Turbo/MAP Decoderxe2x80x9d, submitted to the International Journal of Satellite Communications, Feb. 21, 1997; J. Hagenauer, E. Offer, and L. Papke, xe2x80x9cIterative Decoding of Binary Block and Convolutional Codesxe2x80x9d, IEEE Trans. on Inform Theory, Vol. 42, No. 2, pp. 429-445, March 1996; J. Erfanian, S. Pasupathy, G. Gulak, xe2x80x9cReduced Complexity Symbol Detectors with Parallel Structures for ISI Channelsxe2x80x9d, IEEE Trans. on Communications, Vol. 42, No. 2/3/4, pp.1661-1671, February/March/April 1994.
aJb=ln(ea+eb)=max(a,b)+f(axe2x88x92b)xe2x80x83xe2x80x83(17)
where
f(x)=ln(1+exe2x88x92|x|)xe2x80x83xe2x80x83(18)
The function f(x) can be easily implemented in a small single-parameter lookup table. It has been found that a table size of 16 or more, spanning an input range from 0 to 8, typically results in negligible degradation for Turbo decoding. By extension, the following operation is also defined:                                           J                          n              =              1                        N                    ⁢                      x            n                          =                              x            1                    ⁢          J          ⁢                      xe2x80x83                    ⁢                      x            2                    ⁢                      xe2x80x83                    ⁢          J          ⁢                      xe2x80x83                    ⁢          ⋯          ⁢                      xe2x80x83                    ⁢          J          ⁢                      xe2x80x83                    ⁢                      x            N                                              (        19        )            
With these definitions and tools, the APP algorithm becomes:                               L          i                =                                            J                              m                =                0                                                              N                  s                                -                1                                      ⁢                          A              i              m                                +                      D            i                          0              ,              m                                +                      B                          i              +              1                                      f              ⁡                              (                                  0                  ,                  m                                )                                              -                                    J                              m                =                0                                                              N                  s                                -                1                                      ⁢                          A              i              m                                +                      D            i                          1              ,              m                                +                      B                          i              +              1                                      f              ⁡                              (                                  1                  ,                  m                                )                                                                        (        20        )                                          A          i          m                =                                            J                              d                =                0                            1                        ⁢                          A                              i                -                1                                            b                ⁡                                  (                                      d                    ,                    m                                    )                                                              +                      D                          i              -              1                                      d              ,                              b                ⁡                                  (                                      d                    ,                    m                                    )                                                                                        (        21        )                                          B          i          m                =                                            J                              d                =                0                            1                        ⁢                          D              i                              d                ,                m                                              +                      B                          i              +              1                                      f              ⁡                              (                                  d                  ,                  m                                )                                                                        (        22        )            
where the branch metrics are now given by
xe2x80x83Did,m=Cixe2x88x92Lc(xid+yicd,m)xe2x80x83xe2x80x83(23)
or,
Did,m=Cixe2x80x2+Lc/2(xidxe2x80x2+yicxe2x80x2d,m)xe2x80x83xe2x80x83(24)
Again, the constants Ci and Cxe2x80x2i can be ignored or used to normalize the state metrics since they cancel in (20).
Similar to (11), the log likelihood ratios (LLR""s) can now be expressed as
Li=Lcxi+zixe2x80x83xe2x80x83(25)
where zi=ln(xcex6i) is the extrinsic information in the log domain.
The order of operations for the log-APP algorithm is similar to that for the APP algorithm. The initialization is modified as follows. If the encoder starts in the zero state then initialize A10=0 and A1m=xe2x88x92big for mxe2x89xa00, where big is a number large enough to guarantee that state 0 wins. If the encoder ends in the zero state then initialize BK+10=0 and BK+1m=xe2x88x92big for mxe2x89xa00. If the encoder ends in an unknown state then it is appropriate to initialize all xcex2""s to 0, or some other single value.
The max-log-APP decoding algorithm is now described. The max-log-APP algorithm is obtained by letting f(x)=0 in (18). With this simplification, equations (20) to (22) become
                              L          i                =                                            max              m                        ⁢                          [                                                A                  i                  m                                +                                  D                  i                                      0                    ,                    m                                                  +                                  B                                      i                    +                    1                                                        f                    ⁡                                          (                                              0                        ,                        m                                            )                                                                                  ]                                -                                    max              m                        ⁢                          [                                                A                  i                  m                                +                                  D                  i                                      1                    ,                    m                                                  +                                  B                                      i                    +                    1                                                        f                    ⁡                                          (                                              1                        ,                        m                                            )                                                                                  ]                                                          (        26        )            xe2x80x83Aim=max[Aixe2x88x921b(0,m)+Dixe2x88x9210,b(0,m),Aixe2x88x921b(1,m)+Dixe2x88x9211,b(1,m)]xe2x80x83xe2x80x83(27)
Bim=max[Di0,m+Bi+1f(0,m),Di1,m+Bi+1f(1,m)]xe2x80x83xe2x80x83(28)
The branch metrics are again given by (23) or (24).
A number of important observations can be made about the max-log-APP algorithm. First, it is independent of the noise variance, and thus any scale factors, when computing the branch metrics. Thus, letting Lc=1 in (23) and (24), and dropping the normalization constants which are to be understood, the branch metrics can be reduced to simply
Did,m=xidxe2x88x92yicd,mxe2x80x83xe2x80x83(29)
or
Did,m=xc2xd(xidxe2x80x2+yicxe2x80x2d,m)xe2x80x83xe2x80x83(30)
Recall that dxe2x80x2 and cxe2x80x2 are the xc2x11 transmission symbols corresponding to d and c, as defined in (2) and (3). The factor of xc2xd could also be dropped in (30) if the max-log-APP decoding algorithm is only used once. When used iteratively in a Turbo decoder however, it is important that the output LLR""s be scaled appropriately for reusing the parity channel samples, {yi}, which do not get improved or rescaled.
Another useful observation is that the A""s are calculated in the same way that a Viterbi algorithm calculates its state metrics, given all past channel samples. The B""s are also calculated using the metric portion of a Viterbi algorithm, but going backwards in time using all future samples. When these forward and backward state metrics are combined in (26), along with the branch metrics for the current bit, it is apparent that the max-log-APP algorithm finds the same MLSE sequence as the Viterbi algorithm (given sufficient history depth for all paths to merge). This has also already been noted in P. Robertson, P. Hoeher, and E. Villebrun, xe2x80x9cOptimal and Sub-Optimal Maximum a Posteriori Algorithms Suitable for Turbo Decodingxe2x80x9d, IEEE Communications Theory, Vol. 8, No. 2, pp. 119-125, March-April 1997 and S. Pietrobon, xe2x80x9cImplementation and Performance of a Turbo/MAP Decoderxe2x80x9d, submitted to the International Journal of Satellite Communications, Feb. 21, 1997. One of the differences between the Viterbi algorithm and the max-log-APP algorithm is that the max-log-APP algorithm does not need to keep track of state histories, but requires both forward and backward state metrics. That is, the max-log-APP algorithm does not require the history portion of a Viterbi algorithm. Another important difference is that the Viterbi algorithm does not output soft information about each decision. Although the max-log-APP algorithm does output soft information, it is still suboptimum compared to the information provided by the APP or log-APP algorithms.
FIG. 3 shows a prior art approach to Turbo decoding based on the log-APP decoding algorithm. The Turbo decoder uses an iterative process where the de-interleaved output vector of the second log-APP decoder, L2, is fed back to the input of the first log-APP decoder after the first iteration. The first iteration uses the channel sample vector, X, corresponding to the systematic bits. These samples must be scaled by the channel reliability factor, Lc, if true log-APP decoding is to be performed. The channel sample vectors Y1 and Y2, corresponding to the parity bits from RSC encoders 1 and 2, are never updated and are used in every iteration. These channel samples must also be scaled by Lc for true log-APP decoding.
The extrinsic information vector, Lex, associated with a particular log-APP decoder is defined as the output, Lout, minus the input, Lin. This extrinsic information is saved (delayed) and subtracted off the input to the same log-APP decoder on the next iteration. It is well known that this operation generally improves performance and speeds up the convergence of the Turbo decoder. On the first iteration there is no extrinsic information to be subtracted off, thus this operation can be avoided.
The vector that is input to the second log-APP decoder must be interleaved using the same interleaver that was used in the Turbo-code encoder. Likewise, the output from the second log-APP decoder must be de-interleaved before being fed back to the input of the first log-APP decoder. Decisions can be made either at the output of the first log-APP decoder or the de-interleaved output of the second log-APP decoder. It is convention that one Turbo decoding iteration be defined as two log-APP decoding operations as shown in FIG. 3. To avoid confusion we will generally refer to the number of individual decoding operations, rather than the number of iterations.
FIG. 4 shows a modified Turbo decoder. This approach was briefly described in S. Crozier, A. Hunt, K. Gracie, and J. Lodge, xe2x80x9cPerformance and Complexity Comparison of Block Turbo-Codes, Hyper-Codes, and Tail-Biting Convolutional Codesxe2x80x9d, 19-th Biennial Symposium on Communications, Kingston, Ontario, Canada, pp.84-88, May 31-Jun. 3, 1998 and is also described in a co-pending U.S. patent application No. 60/055,611 filed Aug. 14, 1997. It is similar to the block diagram shown in FIG. 3 for the standard approach to Turbo decoding. One important difference is the use of the lower-complexity max-log-APP decoder, instead of the log-APP decoder, as the component decoder. The max-log-APP decoder is insensitive to scale factors. Thus the systematic and parity channel sample vectors, X, Y1 and Y2, no longer need to be scaled by the channel reliability factor, Lc, and this factor no longer needs to be estimated. Another important difference is the correction of both the total output, Lout, and the extrinsic information, Lex, generated by each max-log-APP decoder.
It has been observed that the extrinsic information generated by the max-log-APP decoder is too optimistic. That is, the magnitude of the extrinsic information generated by the max-log-APP decoder is larger, on average, than that generated by the log-APP decoder. This average magnitude bias is easily corrected using a simple scale factor (SF). The corrected output and corrected extrinsic information vectors are calculated as follows:
Lexn=(Loutnxe2x88x92Linn)xc3x97SF, n=1,2xe2x80x83xe2x80x83(31)
Lcorn=Linn+Lexn, n=1,2xe2x80x83xe2x80x83(32)
where n is the max-log-APP decoder number. The best SF is a function of the signal-to-noise ratio (SNR), the block size, the puncture rate, and the Turbo decoder iteration number. In practice it has been found that SFxe2x89xa7⅝ works well for almost all block sizes, SNRs, and iteration numbers, of practical interest. The improvement over using no scale factor, that is SF=1, depends on the SNR and other parameters, but is typically about 0.3 dB. The degradation from true log-APP decoding is typically within 0.1 or 0.2 dB, depending on the operating point.
The corrected extrinsic information, as calculated in (31), is saved (delayed) and subtracted off the input to the same max-log-APP decoder on the next iteration. As for the original Turbo decoder, the input vector to the second max-log-APP decoder must be interleaved using the same interleaver used in the Turbo-code encoder. Likewise, the corrected output from the second max-log-APP decoder must be de-interleaved before being fed back to the input of the first max-log-APP decoder.
It is an object of the present invention to obviate or mitigate at least one disadvantage of previous systems and methods for Turbo decoding.
It is an object of this invention to provide a reduced-complexity method for max-log-APP processing for use in Turbo and Turbo-like decoders.
It is another object of this invention to provide methods of Turbo decoding with lower processing required for decoding systematic convolutional codes by eliminating a portion of the calculations conventionally associated with max-log-APP processing, without substantially reducing the overall decoder performance.
It is yet another object of the invention to provide an early stopping method that uses the reduced complexity max-log-APP decoder to reduce the average number of decoding operations required by an iterative Turbo decoder.
A first aspect of the present invention provides a method of max-log-APP decoding of a sequence of samples representing a transmitted sequence of symbols obtained from encoding a data sequence of bits, each having a bit time i, with a binary convolutional encoding method having Ns states and an encoding trellis, said decoding method comprising the seven following steps. In the first step the sequence of samples is received, following which a set of branch metrics is computed at each time i from the received sequence of samples in a second step. The third and fourth steps respectively are to compute a set of Ns forward state metrics, and a set of Ns backward state metrics, at each time i, from the set of branch metrics. Following these two steps a maximum metric M for an MLSE sequence corresponding to the received sequence of samples is found, and then the sixth step is to compute maximum of all combined metrics at time i for at least one of the data bit values of 0 and 1, where a combined metric for a bit value at time i is the sum of a forward state metric, a branch metric, and a backward state metric, corresponding to a branch of the encoding trellis for said bit value at time i. The seventh step is to compute at least one output log likelihood ratio, corresponding to the data bit at time i, as the difference between one of the maximum of all combined metrics for data bit values 0 and 1 at time i and the maximum metric M. In embodiments of this aspect of the invention the convolutional encoding method that encoded the transmitted sequence of samples uses systematic convolutional encoding, and optionally may have used recursive systematic convolutional encoding. In other embodiments of the first aspect of the present invention M is computed as either the maximum of the last computed Ns forward state metrics or as the maximum of the last computed Ns backward state metrics. In further embodiments of the present invention the seventh step is performed such that if the maximum of all combined metrics at time i, for data bit 0, is less than the maximum metric M, then the output log likelihood ratio is calculated as the difference between the maximum of all combined metrics at time i, for data bit 0, and M, otherwise the output log likelihood ratio is calculated as the difference between the maximum metric M and the maximum of all combined metrics at time i, for data bit 1, alternatively the seventh step can be performed such that: if the maximum of all combined metrics at time i, for data bit 1, is less than the maximum metric M, then the output log likelihood ratio is calculated as the difference between the maximum metric M and the maximum of all combined metrics at time i, for data bit 1, otherwise the output log likelihood ratio is calculated as the difference between the maximum of all combined metrics at time i, for data bit 0, and M. In a still further embodiment of the present invention where the convolutional encoding method that encoded the transmitted sequence of samples uses systematic convolutional encoding, a set of systematic input log likelihood ratios, Lin, with an i-th element defined by Lin(i), corresponding to the i-th data bit are used as an input, and the seventh step is performed such that if Lin(i) less than 0 and the maximum of all combined metrics at time i, for data bit 0, is less than M then the output log likelihood ratio is calculated as the difference between the maximum of all combined metrics at time i, for data bit 0, and M, if Lin(i) less than 0 and the maximum of all combined metrics at time i, for data bit 0, is greater than or equal to M then the output log likelihood ratio is calculated as the difference between the maximum metric M and the maximum of all combined metrics at time i, for data bit 1; if Lin(i)xe2x89xa70 and the maximum of all combined metrics at time i, for data bit 1, is less than M then the output log likelihood ratio is calculated as the difference between the maximum metric M and the maximum of all combined metrics at time i, for data bit 1, and if Lin(i)xe2x89xa70 and the maximum of all combined metrics at time i, for data bit 1, is greater than or equal to M then the output log likelihood ratio is calculated as the difference between the maximum of all combined metrics at time i, for data bit 0, and M.
In a second aspect of the present invention there is provided a method of max-log-APP decoding of a sequence of samples representing a transmitted sequence of symbols obtained from encoding a data sequence of bits, each having a bit time i, with a binary convolutional encoding method having Ns states and an encoding trellis, said decoding method comprising the eight following steps. In the first step the sequence of samples is received, following which a set of branch metrics, at each time i, from the received sequence of samples is computed. In the third and fourth steps a set of Ns forward state metrics and a set of backward state metrics, at each time i, from the set of branch metrics is computed. In the fifth and sixth steps an MLSE sequence, corresponding to the received sequence of samples is found, and subsequently a maximum metric M for the MLSE sequence is found. The seventh step is to compute the maximum of all combined metrics at time i for one of the data bit values of 0 and 1, where a combined metric for a bit value at time i is the sum of a forward state metric, a branch metric, and a backward state metric, corresponding to a branch of the encoding trellis for said bit value at time i. The eighth step is to compute at least one output log likelihood ratio, corresponding to the data bit at time i, as the difference between one of the maximum of all combined metrics for data bit values 0 and 1 at time i and the maximum metric M. In embodiments of this aspect of the invention the convolutional encoding method that encoded the transmitted sequence of samples uses systematic convolutional encoding, and optionally may have used recursive systematic convolutional encoding. In other embodiments of the first aspect of the present invention M is computed as either the maximum of the last computed Ns forward state metrics or as the maximum of the last computed Ns backward state metrics. In a further embodiments of the present invention the eighth step is performed such that if the i-th bit of the MLSE sequence has a value of 1 then the output log likelihood ratio is calculated as the difference between the maximum of all combined metrics at time i, for data bit 0, and M, otherwise the output log likelihood ratio is calculated as the difference between the maximum metric M and the maximum of all combined metrics at time i, for data bit 1. In other embodiments of the second aspect of the present invention the third and fifth steps are combined to implement a step of computing a set of forward state metrics and an MLSE sequence using a Viterbi decoding method, or the fourth and fifth steps are combined to implement a step of computing a set of backward state metrics and an MLSE sequence using a Viterbi decoding method. Alternatively, the MLSE sequence can be determined using one of the sets of forward and backward state metrics and a method of state metric retrace.
A third aspect of the present invention provides a method of iterative decoding of a sequence of samples representing a transmitted sequence of symbols obtained from encoding a data sequence of bits with a plurality of convolutional encoders, said decoding method comprising the steps of receiving said sequence of samples and performing Ndec decoding operations each corresponding to one of the convolutional encoders. In this aspect, Ndec is at least 3, each of the first Ndecxe2x88x921 decoding operations uses a method of soft-in/soft-out decoding, to provide a soft input for the next decoding operation the final Ndec-th decoding operation uses a method of MLSE decoding to determine an MLSE sequence and at least two of the Ndec decoding operations correspond to the same convolutional encoder. In embodiments of the present aspect of the invention at least one of the first Ndecxe2x88x921 decoding operations uses a method of log-APP decoding or a method of max-log-APP decoding, and the final decoding operation uses a Viterbi decoding method to determine the MLSE sequence, or the final decoding operation computes state metrics and uses a method of state metric retrace to determine the MLSE sequence. Alternatively the final decoding operation can use a method of max-log-APP decoding with an extrinsic information scale factor of one to determine the MLSE sequence.
In another aspect of the present invention there is provided a method of iterative decoding of a sequence of samples representing a transmitted sequence of symbols obtained from encoding a data sequence of bits with a plurality of convolutional encoders, said decoding method comprising the following steps. The first step is to receive the sequence of samples. The second step is to perform Ndec decoding operations each corresponding to one of the convolutional encoders, where Ndec is at least 2, wherein each of the first Ndecxe2x88x921 decoding operations uses a method of soft-in/soft-out decoding, to provide a soft input for the next decoding operation, and where at least one of the first Ndecxe2x88x921 decoding operations computes a set of Ns forward state metrics and a set of Ns backward state metrics, at each time i, from a set of branch metrics computed from a sequence of samples from the output of the previous decoding operation; finds a maximum metric M for an MLSE sequence corresponding to the sequence of samples from the output of the previous decoding operation; computes the maximum of all combined metrics at time i for at least one of the data bit values of 0 and 1, where a combined metric for a bit value at time i is the sum of one of the set of Ns forward state metrics, a branch metric from the set of branch metrics, and one of the set of Ns backward state metrics, corresponding to a branch of the encoding trellis for said bit value at time i; and computes at least one output log likelihood ratio, corresponding to the data bit at time i, as the difference between one of the maximum of all combined metrics for data bit values 0 and 1 at time i and the maximum metric M; and the final Ndecth decoding operation uses a method of MLSE decoding to determine an MLSE sequence.
In another aspect of the present invention there is provided a method of iterative decoding of a sequence of samples representing a transmitted sequence of symbols obtained from encoding a data sequence of bits with a plurality of convolutional encoders, said decoding method comprising the steps of receiving said sequence of samples and performing Ndec decoding operations each corresponding to one of the convolutional encoders, where Ndec is at least 2. In this aspect each of the first Ndecxe2x88x921 decoding operations uses a method of soft-in/soft-out decoding, to provide a soft input for the next decoding operation, where at least one of the first Ndecxe2x88x921 decoding operations computes a set of Ns forward state metrics and a set of Ns backward state metrics, at each time i, from a set of branch metrics computed from a sequence of samples from the output of the previous decoding operation; finds an MLSE sequence, corresponding to the sequence of samples from the output of the previous decoding operation, finds a maximum metric M for an MLSE sequence corresponding to the sequence of samples from the output of the previous decoding operation; computes the maximum of all combined metrics at time i for one of the data bit values of 0 and 1, where a combined metric for a bit value at time i is the sum of one of the set of Ns forward state metrics, a branch metric from the set of branch metrics, and one of the set of Ns backward state metrics, corresponding to a branch of the encoding trellis for said bit value at time i; and computes at least one output log likelihood ratio, corresponding to the data bit at time i, as the difference between one of the maximum of all combined metrics for data bit values 0 and 1, at time i and the maximum metric M and the final Ndecth decoding operation uses a method of MLSE decoding to determine an MLSE sequence.
In another aspect of the present invention there is provided a method of iterative decoding of a sequence of samples representing a transmitted sequence of symbols obtained from encoding a data sequence of bits with a plurality of systematic convolutional encoders, said decoding method comprising the following nine steps. The first step is to receive the sequence of samples. The second step is to specify a maximum number Dmax of decoding operations, where Dmax is at least 2, and each decoding operation corresponds to one of the systematic convolutional encoders. The third step is to specify a minimum number Dmin of decoding operations, where Dmin is at least 1, and then to specify a preferred number Dag of consecutive agreements, between two consecutive MLSE sequences, where Dag is at least 1. Then the number of decoding operations is counted and stored as Ndec, which is subsequently tested to see if it is equal to Dmax. When the test is true the iterative decoding method is stopped. The eighth step is to count the number of consecutive agreements, Nag, between two consecutive MLSE sequences and then to test if Nag is equal to Dag and stopping the iterative decoder method when true. In the above described aspect each of the first Ndecxe2x88x921 decoding operations uses a method of soft-in/soft-out decoding, each decoding operation from Dminxe2x88x92Dag to Ndecxe2x88x921 uses a first method of MLSE decoding to find an MLSE sequence, the final Ndec-th decoding operation uses a second method of MLSE decoding to find a final MLSE sequence and if Dminxe2x88x92Dag=0 then the 0-th MLSE sequence is determined from a systematic portion of the received sequence of samples independent of any decoding operations. In embodiments of the present aspect the soft-in/soft-out decoding method can use a method of log-APP decoding or a method of max-log-APP decoding. Additionally the second method of MLSE decoding can use a Viterbi decoding method to determine the final MLSE sequence or the second method of MLSE decoding computes state metrics and uses a method of state metric retrace to determine the final MLSE sequence. Alternatively the second method of MLSE decoding uses a method of max-log-APP decoding with an extrinsic information scale factor of one to determine the final MLSE sequence. Another embodiment of the present aspect further comprises the step of specifying a maximum number of iterative decoding repetitions, Imax, where Imax is at least 1 prior to receiving said sequence of samples, and following the eighth step, the steps of counting the number of iterative decoding repetitions performed as Nit; and performing a test if Ndec is equal to Dmax and if Nag is less than Dag and if Nit is less than Imax; such that if the test is true, then a further repetition is performed wherein a sequence of decoding operations is different from a corresponding sequence of decoding operations used in all previous repetitions of iterative decoding.
In another aspect of the present invention there is provided a method of iterative decoding of a sequence of samples representing a transmitted sequence of symbols obtained from encoding a data sequence of bits with a plurality of convolutional encoders, said decoding method comprising the steps of receiving said sequence of samples and performing Ndec decoding operations each corresponding to one of the convolutional encoders, where Ndec is at least 2. In this aspect of the present invention Ndec is equal to N1+N2, where N1 is a number of first decoding operations and is at least 1, and N2 is a number of second decoding operations and is at least 1, each of the N1 first decoding operations uses a method of log-APP decoding and each of the N2 second decoding operations uses a method of max-log-APP decoding. In an embodiment of this aspect of the present invention a method of early stopping based on comparing consecutive MLSE sequences where each MLSE sequence corresponds to one of the decoding operations is included.
In another aspect of the present invention there is provided a method of iterative decoding off a sequence of samples representing a transmitted sequence of symbols obtained from encoding a data sequence of bits with a plurality of convolutional encoders, said decoding method comprising the steps of receiving said sequence of samples and performing Ndec decoding operations each corresponding to one of the convolutional encoders, where Ndec is at least 3. In this aspect of the present invention Ndec equals N1+N2+1, where N1 is a number of first decoding operations and is at least 1, N2 is a number of second decoding operations and is at least 1, and there is a single third decoding operation, each of the N1 first decoding operations uses a method of log-APP decoding, each of the N2 second decoding operations uses a method of max-log-APP decoding and the single third decoding operation uses a method of MLSE decoding. In an embodiment of the present aspect of the invention a method of early stopping based on comparing consecutive MLSE sequences where each MLSE sequence corresponds to one of the decoding operations is included.
Other aspects and features of the present invention will become apparent to those ordinarily skilled in the art upon review of the following description of specific embodiments of the invention in conjunction with the accompanying figures.